Search Results

Documents authored by Aubrun, Nathalie

Document
DOI: 10.4230/LIPIcs.STACS.2020.26
Domino Problem Under Horizontal Constraints

Authors: Nathalie Aubrun, Julien Esnay, and Mathieu Sablik

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
The Domino Problem on ℤ² asks if it is possible to tile the plane with a given set of Wang tiles; it is a classical decision problem which is known to be undecidable. The purpose of this article is to parameterize this problem to explore the frontier between decidability and undecidability. To do so we fix some horizontal constraints H on the tiles and consider a new Domino Problem DP_H: given a vertical constraint, is it possible to tile the plane? We characterize the nearest-neighbor horizontal constraints where DP_H is decidable using graphs combinatorics.
Cite as

Nathalie Aubrun, Julien Esnay, and Mathieu Sablik. Domino Problem Under Horizontal Constraints. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aubrun_et_al:LIPIcs.STACS.2020.26,
  author =	{Aubrun, Nathalie and Esnay, Julien and Sablik, Mathieu},
  title =	{{Domino Problem Under Horizontal Constraints}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.26},
  URN =		{urn:nbn:de:0030-drops-118875},
  doi =		{10.4230/LIPIcs.STACS.2020.26},
  annote =	{Keywords: Dynamical Systems, Symbolic Dynamics, Subshifts, Wang tiles, Undecidability, Domino Problem, Combinatorics, Tilings, Subshifts of Finite Type}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.46
The Domino Problem is Undecidable on Surface Groups

Authors: Nathalie Aubrun, Sebastián Barbieri, and Etienne Moutot

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We show that the domino problem is undecidable on orbit graphs of non-deterministic substitutions which satisfy a technical property. As an application, we prove that the domino problem is undecidable for the fundamental group of any closed orientable surface of genus at least 2.
Cite as

Nathalie Aubrun, Sebastián Barbieri, and Etienne Moutot. The Domino Problem is Undecidable on Surface Groups. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{aubrun_et_al:LIPIcs.MFCS.2019.46,
  author =	{Aubrun, Nathalie and Barbieri, Sebasti\'{a}n and Moutot, Etienne},
  title =	{{The Domino Problem is Undecidable on Surface Groups}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.46},
  URN =		{urn:nbn:de:0030-drops-109900},
  doi =		{10.4230/LIPIcs.MFCS.2019.46},
  annote =	{Keywords: tilings, substitutions, SFTs, decidability, domino problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1833
An Order on Sets of Tilings Corresponding to an Order on Languages

Authors: Nathalie Aubrun and Mathieu Sablik

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
Traditionally a tiling is defined with a finite number of finite forbidden patterns. We can generalize this notion considering any set of patterns. Generalized tilings defined in this way can be studied with a dynamical point of view, leading to the notion of subshift. In this article we establish a correspondence between an order on subshifts based on dynamical transformations on them and an order on languages of forbidden patterns based on computability properties.
Cite as

Nathalie Aubrun and Mathieu Sablik. An Order on Sets of Tilings Corresponding to an Order on Languages. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 99-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{aubrun_et_al:LIPIcs.STACS.2009.1833,
  author =	{Aubrun, Nathalie and Sablik, Mathieu},
  title =	{{An Order on Sets of Tilings Corresponding to an Order on Languages}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{99--110},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1833},
  URN =		{urn:nbn:de:0030-drops-18336},
  doi =		{10.4230/LIPIcs.STACS.2009.1833},
  annote =	{Keywords: Tiling, Subshift, Turing machine with oracle, Subdynamics}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact